SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Selective Repeat ARQ</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Selective Repeat ARQ</span></span>

</h1>

</header>

</p><p><b>Selective Repeat ARQ</b> or <b>Selective Reject ARQ</b> is a specific instance of the <a href="Automatic_repeat_request" title="Automatic repeat request">automatic repeat request</a> (ARQ) protocol used to manage sequence numbers and retransmissions in <a href="Reliable_communications" class="mw-redirect" title="Reliable communications">reliable communications</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Summary">Summary</h2></div>

<p>Selective Repeat is part of the automatic repeat request (ARQ). With selective repeat, the sender sends a number of frames specified by a window size even without the need to wait for individual ACK from the receiver as in <a href="Go-Back-N_ARQ" title="Go-Back-N ARQ">Go-Back-N ARQ</a>. The receiver may selectively reject a single frame, which may be retransmitted alone; this contrasts with other forms of ARQ, which must send every frame from that point again. The receiver accepts out-of-order frames and buffers them. The sender individually retransmits frames that have timed out.

</p>

<div class="mw-heading mw-heading2"><h2 id="Concept">Concept</h2></div>

<p>It may be used as a protocol for the delivery and acknowledgement of message units, or it may be used as a protocol for the delivery of subdivided message sub-units.

</p><p>When used as the protocol for the delivery of <b>messages</b>, the sending process continues to send a number of <a href="Data_frame" class="mw-redirect" title="Data frame">frames</a> specified by a <i>window size</i> even after a frame loss. Unlike <a href="Go-Back-N_ARQ" title="Go-Back-N ARQ">Go-Back-N ARQ</a>, the receiving process will continue to accept and <a href="Acknowledgement_(data_networks)" title="Acknowledgement (data networks)">acknowledge</a> frames sent after an initial error; this is the general case of the <a href="Sliding_window_protocol" title="Sliding window protocol">sliding window protocol</a> with both transmit and receive window sizes greater than 1.

</p><p>The receiver process keeps track of the sequence number of the earliest frame it has not received, and sends that number with every <a href="Acknowledgement_(data_networks)" title="Acknowledgement (data networks)">acknowledgement</a> (ACK) it sends. If a frame from the sender does not reach the receiver, the sender continues to send subsequent frames until it has emptied its <i>window</i>. The receiver continues to fill its receiving window with the subsequent frames, replying each time with an ACK containing the sequence number of the earliest missing <a href="Data_frame" class="mw-redirect" title="Data frame">frame</a>. Once the sender has sent all the frames in its <i>window</i>, it re-sends the frame number given by the ACKs, and then continues where it left off.

</p><p>The size of the sending and receiving windows must be equal, and half the maximum sequence number (assuming that sequence numbers are numbered from 0 to <i>n</i>−1) to avoid miscommunication in all cases of packets being dropped. To understand this, consider the case when all ACKs are destroyed. If the receiving window is larger than half the maximum sequence number, some, possibly even all, of the packets that are present after timeouts are duplicates that are not recognized as such. The sender moves its window for every packet that is acknowledged.<sup id="cite_ref-Tanenbaum_1-0" class="reference"><a href="#cite_note-Tanenbaum-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>When used as the protocol for the delivery of <b>subdivided messages</b> it works somewhat differently. In non-continuous channels where messages may be variable in length, standard ARQ or Hybrid ARQ protocols may treat the message as a single unit. Alternately selective retransmission may be employed in conjunction with the basic ARQ mechanism where the message is first subdivided into sub-blocks (typically of fixed length) in a process called <a href="Packet_segmentation" title="Packet segmentation">packet segmentation</a>. The original variable length message is thus represented as a concatenation of a variable number of sub-blocks. While in standard ARQ the message as a whole is either acknowledged (ACKed) or negatively acknowledged (NAKed), in ARQ with selective transmission the ACK response would additionally carry a bit flag indicating the identity of each sub-block successfully received. In ARQ with selective retransmission of sub-divided messages each retransmission diminishes in length, needing to only contain the sub-blocks that were linked.

</p><p>In most channel models with variable length messages, the probability of error-free reception diminishes in inverse proportion with increasing message length. In other words, it's easier to receive a short message than a longer message. Therefore, standard ARQ techniques involving variable length messages have increased difficulty delivering longer messages, as each repeat is the full length. Selective re-transmission applied to variable length messages completely eliminates the difficulty in delivering longer messages, as successfully delivered sub-blocks are retained after each transmission, and the number of outstanding sub-blocks in following transmissions diminishes. Selective Repeat is implemented in UDP transmission.

</p>

<div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2></div>

<p>These examples assume an infinite number of sequence and request numbers.<sup id="cite_ref-KuroseRoss_2-0" class="reference"><a href="#cite_note-KuroseRoss-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<pre><i>N</i>  := window size

<i>Rn</i> := request number

<i>Sn</i> := sequence number

<i>Sb</i> := sequence base

<i>Sm</i> := sequence max

<i>buffer[]</i> := buffer to store out-of-order packets

<b>function</b> receiver <b>is</b>

<i>Rn</i> := 0

<i>buffer</i> := empty

Do the following forever:

<b>if</b> the packet received is error-free and <i>Sn</i> = <i>Rn</i> <b>then</b>

Accept the packet and send it to a higher layer

<i>Rn</i> := <i>Rn</i> + 1

<b>while</b> <i>buffer[Rn]</i> exists <b>do</b>

Accept the packet from the buffer and send it to a higher layer

Remove packet Rn from the buffer

<i>Rn</i> := <i>Rn</i> + 1

<b>else if</b> the packet received is error-free and <i>Sn</i> > <i>Rn</i> <b>then</b>

Buffer the packet at position <i>Sn</i>

Ignore packet

Send a Request for <i>Rn</i>

<b>function</b> sender <b>is</b>

<i>Sb</i> := 0

<i>Sm</i> := <i>N</i> + 1

<i>buffer</i> := empty

Repeat the following steps forever:

<b>if</b> you receive a request number where <i>Rn</i> > <i>Sb</i> <b>then</b>

Remove packets with <i>Sn</i> < <i>Rn</i> from the <i>buffer</i>

<b>if</b> no packet is in transmission <b>then</b>

Transmit a packet where <i>Sb</i> ≤ <i>Sn</i> < <i>Sm</i>

Store the transmitted packet in the buffer

<b>for each</b> packet <i>Sn</i> in buffer <b>do</b>

<b>if</b> packet <i>Sn</i> timeout occurred <b>then</b>

Retransmit packet <i>Sn</i>

</pre>

<div class="mw-heading mw-heading2"><h2 id="Choosing_a_window_size_(N)">Choosing a window size (<i>N</i>)</h2></div>

<p>There are a few things to keep in mind when choosing a value for <var style="padding-right: 1px;">N</var> in Selective Repeat ARQ:

</p>

<ol><li>The sender must not transmit faster than the receiver can handle. <var style="padding-right: 1px;">N</var> should be bounded by the receiver’s capacity to process and buffer out-of-order packets.</li>

<li><var style="padding-right: 1px;">N</var> must be less than half the total number of sequence numbers (if they are numbered from zero to the maximum value of the sequence number space) to avoid ambiguity in detecting duplicate packets and dropped acknowledgments.<sup id="cite_ref-Tanenbaum_1-1" class="reference"><a href="#cite_note-Tanenbaum-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></li>

<li>Considering the constraints in (1) and (2), choose <var style="padding-right: 1px;">N</var> to be as large as possible to maximize throughput.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup></li></ol>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<p>The <a href="Transmission_Control_Protocol" title="Transmission Control Protocol">Transmission Control Protocol</a> uses a variant of <a href="Go-Back-N_ARQ" title="Go-Back-N ARQ">Go-Back-N ARQ</a> to ensure reliable transmission of data over the <a href="Internet_Protocol" title="Internet Protocol">Internet Protocol</a>, which does not provide guaranteed delivery of packets; with <a href="Transmission_Control_Protocol#Selective_acknowledgments" title="Transmission Control Protocol">Selective Acknowledgement (SACK) extension</a>, it may also use Selective Repeat ARQ.

</p><p>The <a href="ITU-T" title="ITU-T">ITU-T</a> <a href="G.hn" title="G.hn">G.hn</a> standard, which provides a way to create a high-speed (up to 1 Gigabit/s) <a href="Local_area_network" title="Local area network">Local area network</a> using existing home wiring (<a href="Power_line_communication" class="mw-redirect" title="Power line communication">power lines</a>, phone lines and <a href="Ethernet_over_coax" title="Ethernet over coax">coaxial cables</a>), uses Selective Repeat ARQ to ensure reliable transmission over noisy media. <a href="G.hn" title="G.hn">G.hn</a> employs <a href="Packet_segmentation" title="Packet segmentation">packet segmentation</a> to sub-divide messages into smaller units, to increase the probability that each one is received correctly.

</p><p>The <a href="STANAG_5066" title="STANAG 5066">STANAG 5066</a> Profile for High Frequency (HF) Radio Data Communication uses selective repeat ARQ, with a maximum window size of 128 protocol-data units (PDUs).

</p>

<li><a href="Reliable_Data_Transfer" title="Reliable Data Transfer">Reliable Data Transfer</a></li>

<li><a href="Pipeline_(software)" title="Pipeline (software)">Pipeline (software)</a></li>

<li><a href="Automatic_repeat_request" title="Automatic repeat request">Automatic repeat request</a></li>

<li><a href="Computer_networking" class="mw-redirect" title="Computer networking">Computer networking</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFTanenbaum2003" class="citation book cs1">Tanenbaum, Andrew S. (2003). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/computernetworks00tane_2"><i>Computer Networks</i></a></span> (4th ed.). Prentice Hall. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-13-066102-3</bdi>.</cite></span>

</li>

<li id="cite_note-KuroseRoss-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-KuroseRoss_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFKuroseKeith_W._Ross" class="citation book cs1">Kurose, James F.; Keith W. Ross. <i>Computer Networking: A Top-Down Approach</i>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-321-49770-8</bdi>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFMarbach" class="citation web cs1">Marbach, Peter. <a rel="nofollow" class="external text" href="http://www.cs.toronto.edu/~marbach/COURSES/CSC358_S14/l4.pdf">"ARQ Protocols"</a> <span class="cs1-format">(PDF)</span><span class="reference-accessdate">. Retrieved <span class="nowrap">August 24,</span> 2013</span>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFLockittGatfieldDobyns1975" class="citation conference cs1">Lockitt, J. A.; Gatfield, A. G.; Dobyns, T. R. (1975). <i>A Selective Repeat ARQ system</i>. 3rd International Conference on Digital Satellite Communications. <i>3rd International Conference on Digital Satellite Communications</i>. pp. <span class="nowrap">189–</span>195. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1975dsc..conf..189L">1975dsc..conf..189L</a>.</cite></li>

<li><cite id="CITEREFWeldon1982" class="citation journal cs1">Weldon, E. (March 1982). "An Improved Selective-Repeat ARQ Strategy". <i>IEEE Transactions on Communications</i>. <b>30</b> (3): <span class="nowrap">480–</span>486. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1982ITCom..30..480W">1982ITCom..30..480W</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTCOM.1982.1095497">10.1109/TCOM.1982.1095497</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0090-6778">0090-6778</a>.</cite></li>

<li><cite id="CITEREFComroeD._Costello1984" class="citation journal cs1">Comroe, R.; D. Costello (July 1984). "ARQ schemes for data transmission in mobile radio systems". <i>IEEE Journal on Selected Areas in Communications</i>. <b>2</b> (4): <span class="nowrap">472–</span>481. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1984IJSAC...2..472C">1984IJSAC...2..472C</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FJSAC.1984.1146084">10.1109/JSAC.1984.1146084</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:22759443">22759443</a>.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-12-17" href="https://en.wikipedia.org/wiki/?title=Selective_Repeat_ARQ&oldid=1263612647">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>